/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class RangeSumQuery2D {
    int sums[][];
    public RangeSumQuery2D(int[][] matrix) {
        int rowNums=matrix.length;
        if(rowNums==0){
            sums=matrix;
            return;
        }
        int colNums=matrix[0].length;
        if(colNums==0){
            sums=matrix;//?行1，列0
            return;
        }
        sums=new int[rowNums][colNums];
        for(int i=0;i<rowNums;i++){
            for(int j=0;j<colNums;j++){
                if(j>0&&i>0){
                    sums[i][j]=sums[i][j-1]-sums[i-1][j-1]+sums[i-1][j]+matrix[i][j];
                }else if(i>0){//第一列
                    sums[i][j]=sums[i-1][j]+matrix[i][j];
                }else if(j>0){//第一行
                    sums[i][j]=sums[i][j-1]+matrix[i][j];
                }else{//0 0
                    sums[i][j]=matrix[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1>0&&col1>0){
            return sums[row2][col2]-sums[row1-1][col2]-sums[row2][col1-1]+sums[row1-1][col1-1];
        }
        if(row1>0){//col1==0
            return sums[row2][col2]-sums[row1-1][col2];
        }
        if(col1>0){//row1==0
            return sums[row2][col2]-sums[row2][col1-1];
        }
        return sums[row2][col2];//row1==0&&col1==0
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] matrix={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
		int[][] tests={{2,1,4,3},{1,1,2,2},{1,2,2,4}};
		RangeSumQuery2D rangeSumQuery2D=new RangeSumQuery2D(matrix);
		for (int i = 0; i < tests.length; i++) {
			int[] thisTest=tests[i];
			System.err.println(rangeSumQuery2D.sumRegion(thisTest[0],thisTest[1],thisTest[2], thisTest[3]));
		}
	}

}
